package club.vann.nowcoder;

/**
 * <p>难度：Easy</p>
 * <p>题目：子数组的最大累加和问题</p>
 * <p>描述：给定一个数组arr，返回子数组的最大累加和
 * 例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
 * 题目保证没有全为负数的数据
 * [要求]
 * 时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)
 *
 * 示例1
 * 输入
 * 复制
 * [1, -2, 3, 5, -2, 6, -1]
 * 返回值
 * 复制
 * 12
 * 备注:
 * 1 \leq N \leq 10^51≤N≤10
 * 5
 *
 * |arr_i| \leq 100∣arr
 * i
 * ​
 *  ∣≤100</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-04-20:15:36:41
 */
public class NC19 {
    public static void main(String[] args) {
        NC19 nc19 = new NC19();

        System.out.println("Result["+TestCase.ANS+"] : " + nc19.maxsumofSubarray(TestCase.ARR));
    }

    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxsumofSubarray (int[] arr) {
        // write code here
        int n = arr.length;
        int pre = arr[0];
        int ans = pre;

        for(int i = 1; i < n; i ++) {
            pre = Math.max(pre+arr[i], arr[i]);
            ans = Math.max(ans, pre);
        }

        return ans;
    }

    static class TestCase {
        public static int ANS = 12;
        public static int[] ARR = {1, -2, 3, 5, -2, 6, -1};
    }
}
